DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2017.27

Graphic TSP in Cubic Graphs

Authors: Zdenek Dvorák, Daniel Král, and Bojan Mohar

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract

We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.

Cite as

Zdenek Dvorák, Daniel Král, and Bojan Mohar. Graphic TSP in Cubic Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.STACS.2017.27,
  author =	{Dvor\'{a}k, Zdenek and Kr\'{a}l, Daniel and Mohar, Bojan},
  title =	{{Graphic TSP in Cubic Graphs}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.27},
  URN =		{urn:nbn:de:0030-drops-70068},
  doi =		{10.4230/LIPIcs.STACS.2017.27},
  annote =	{Keywords: Graphic TSP, approximation algorithms, cubic graphs}
}

Search Results

Documents authored by Král, Daniel

Graphic TSP in Cubic Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message